#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll Maxn=410;
ll n,a[Maxn],b[Maxn],p[Maxn],ans;
vector<ll>e[Maxn]; 
int main(){
	freopen("light.in","r",stdin);
	freopen("light.out","w",stdout);
	scanf("%lld",&n);
	srand(998244353);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=a[i];
	for(ll i=1,u,v;i<n;i++){
		scanf("%lld%lld",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(ll i=1;i<=n;i++) p[i]=i;
	if(n<=10){
		do{
			ll res=0;
			for(ll i=1;i<=n;i++){
				res+=a[p[i]];
				for(auto j:e[p[i]]){
					a[j]+=a[p[i]];
				}
			}
			for(ll i=1;i<=n;i++) a[i]=b[i];
			ans=max(ans,res);
		}while(next_permutation(p+1,p+n+1));
		printf("%lld",ans);
		return 0;
	}
	else{
		ll cnt=0;
		ll res=0;
		for(ll i=1;i<=n;i++){
			res+=a[p[i]];
			for(auto j:e[p[i]]){
				a[j]+=a[p[i]];
			}
		}
		for(ll i=1;i<=n;i++) a[i]=b[i];
		ans=max(ans,res);
		res=0;
		for(ll i=n;i;i--){
			res+=a[p[i]];
			for(auto j:e[p[i]]){
				a[j]+=a[p[i]];
			}
		}
		for(ll i=1;i<=n;i++) a[i]=b[i];
		ans=max(ans,res);
		while(cnt<=1e5){
			++cnt;
			random_shuffle(p+1,p+n);		
			ll res=0;
			for(ll i=1;i<=n;i++){
				res+=a[p[i]];
				for(auto j:e[p[i]]){
					a[j]+=a[p[i]];
				}
			}
			for(ll i=1;i<=n;i++) a[i]=b[i];
			ans=max(ans,res);
		}
		printf("%lld",ans);
		return 0;
	}
	return 0;
}
/*
5
1 2 3 4 5
1 2
1 3
2 4
2 5
*/
